package 题目集.线段树or树状数组.线段树;

public class HowManySpace {

    // 范围l~r，信息存在独立数组的i位置
    // 返回递归展开的过程中出现的最大编号
    public static int maxi(int l, int r, int i) {
        if (l == r) {
            return i;
        } else {
            int mid = (l + r) >> 1;
            return Math.max(maxi(l, mid, i << 1), maxi(mid + 1, r, i << 1 | 1));
        }
    }

    public static void main(String[] args) {
        int n = 10000;
        int a = 0;
        int b = 0;
        double t = 0;
        double diff = 0;
        int a2 = 1, n4Max = 0, logx = 0;
        for (int i = 1; i <= n; i++) {
            int space = maxi(1, i, 1);
            double times = (double) space / (double) i;
            double v = lenS(i);
            double n4 = 4 * i;
//            System.out.println("范围[1~" + i + "]，" + "需要空间" + space + "，倍数=" + times + ";\tlog法=" + v + "，4n法=" + n4);
            if (times > t) {
                a = i;
                b = space;
                t = times;
            }
            if (v > n4) throw new RuntimeException("v大了");
            if (n4 - v > diff) {
                diff = n4 - v;
                a2 = i;
                n4Max = (int) n4;
                logx = (int) v;
            }
        }
        System.out.println("其中的最大倍数，范围[1~" + a + "]，" + "需要空间" + b + "，倍数=" + t);
        System.out.println("其中的最大倍数，范围[1~" + a2 + "]，" + "4n空间" + n4Max + "，差值=" + diff + ",logx=" + logx);
        int maxi = maxi(1, 262144, 1);
        System.out.println(maxi);

    }
    static {
        System.out.println(lenS(4));
    }

    public static double lenS(int n) {
        return Math.pow(2, Math.ceil(Math.log(n) / Math.log(2)) + 1);
    }
}
